package demo.practice.dp;

import java.util.Arrays;

public class P740 {
    public static void main(String[] args) {
        P740 p740 = new P740();
        p740.deleteAndEarn(new int[]{3, 4, 2});
    }

    public int deleteAndEarn(int[] nums) {
        Arrays.sort(nums);

        int[] ts = new int[nums[nums.length - 1] + 1];
        for (int num : nums) {
            ts[num]+=1;//计数
        }

        int[] dp =new int[ts.length];


        dp[0]= ts[0];
        dp[1]= Math.max(ts[0],ts[1]);

        for(int i=2;i<dp.length;i++){
            dp[i]= Math.max( dp[i-1] ,dp[i-2]+ ts[i]*i );
        }

        return dp[ts.length-1];
    }
}
